In a communications system, channel encoding is generally used to improve reliability of data transmission and ensure quality of communication. The Polar code has been proved to be a good code that can achieve a Shannon capacity and has low encoding and decoding complexity. The Polar code is a linear block code. A generator matrix thereof is GN., and an encoding process thereof is x1N=u1NGN., where GN.=BN, and a code length N=2n, where n≧0. u1N is input bits, including information bits and frozen bits. Herein,
      F    =          [                                    1                                0                                                1                                1                              ]        ,and BN is a transposed matrix, for example, a bit reversal matrix.  is a Kronecker power of F, and is defined as =F. The Polar code may be expressed by using a coset code (N, K, A, uAC), and an encoding process thereof is x1N=uAGN.(A)⊕uACGN.(AC), where A is a set of indexes of information bits, GN.(A) is a submatrix of GN. and is obtained by using rows that correspond to the indexes in the set A, and GN.(AC) is a submatrix of GN. and is obtained by using rows that correspond to indexes in the set AC. uAC is frozen bits, where a quantity of the frozen bits is (N−K) and the frozen bits are known bits. For simplicity, these frozen bits may be set to 0.
The Polar code may also be decoded by means of maximum likelihood (ML), and a maximum likelihood decoder for ML decoding finds an information bit sequence, to minimize a squared Euclidean distance:
      E    min    =            min              u        k              ⁢                                                y            1            N                    -                                    z              1              N                        ⁡                          (                                                u                  1                                ,                                  u                  2                                ,                …                ⁢                                                                  ,                                  u                  N                                            )                                                  2      
where zk is a symbol obtained after BPSK mapping, where zk=(1−2xk),k=1, . . . , N.
Complexity of ML decoding is O(2^K).
It can be seen that, in the prior art, ML decoding for the Polar code has excessively high complexity.